Electronic money (e-money) comes in the same forms as ordinary money. For example, there are electronic equivalents of checks (e-checks) and electronic equivalents of cash (e-cash).
Electronic checks are easier to implement than electronic cash. In a paper check, the most important component is the user's signature. This signature is supposed to insure the correctness of an obligation to transfer a certain amount of money from the signer ("payer") to a specified payee. In addition, certain properties of the paper of which the check is made are designed so that changes to the content of the paper check will be noticeable. All of these properties are inherent to digital signatures (see e.g., W. Diffie, M. Hellman, "New Directions in Cryptography" IEEE Trans. IT. 1976 and R. Rivest, A. Shamir, and L. Adelman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems", CACM, vol. 21, 1978, pp. 120-126). Thus, it is straightforward to implement digital checks. Similarly, it is easy to implement digital credit cards. A digital signature in this case indicates the authenticity of the user and the user's consent to a particular transaction.
It is harder to create the digital equivalent of cash. (For a discussion of e-cash, see e.g., D. Chaum, et al. "Untraceable Electronic Cash", Proc. Crypto 1988, D. Chaum "Achieving Electronic Privacy" Scientific American, August 1992, pp 96-101, S. Brand "Electronic Cash Systems Based on the Representation Problem in Groups of Prime Order" Proceedings of Crypto '93 Santa Barbara 1993 pp 26-26.15; S. Even et al. "Electronic Wallet" Proc. Crypto '83). The main problem is this. Suppose that a bunch of digital bits represents a coin. What can prevent the payer from double spending the digital coin?
Two approaches have been used in the prior art to resolve this problem. Prevention and after the fact detection. For example, to prevent double spending, tamper resistant devices may be used. Such devices, called electronic wallets (e-wallets) or money modules, store a user's balance in a manner so that even the owner of the device cannot illegally modify the balance. A balance on one of these money modules can change if two such devices "agree" to a specified transaction, whereby one money module (the payer) agrees to pay X dollars to another money module (the payee). In this case, the balance in each money module is changed so that the sum of the two balances remains unchanged. A transaction between a bank and a user is similar except that it involves additional steps such as moving money from the user's checking account into the user's money module where the money now becomes e-cash. The use of tamper-resistant devices, i.e. money modules, to prevent the double spending of e-cash is preferred by banks because banks want to prevent double spending, not detect double spending after such double spending occurs.
However, it is impossible to create a 100% tamper proof money module type device. It is only a question of resources devoted to reverse engineering and decription, etc. If by gaining unauthorized access or "unwrapping" one money module one could forge ten million dollars, then it makes economic sense (but not moral sense) to invest one million dollars to penetrate the money module. There is a spectrum of tamper-resistant technologies that range in price and quality and some economic optimum must be reached.
This optimum is less expensive if a second line of defense can be added. Such a second line of defense might be the use of a process which provides for after the fact exposure of the double spender.
Another issue that arises in connection with the use of e-cash is privacy. For large transactions (e.g. buying a house), traceable forms of e-money such as e-checks can be used. Usually these kinds of transactions are not viewed as secret transactions and usually the parties want evidence as to these transactions. Electronic cash (e-cash) is generally used for smaller daily transactions (e.g. buying groceries and buying newspapers, etc.). A user would not want a government or large private agency a bank) to be able to constantly know his/her whereabouts and the details of daily purchases based on the payment of e-cash to various payees. Thus, after ordinary legitimate uses, the identity of an e-cash spender should not be traceable. On the other hand, the e-cash system should enable detection of the identity of a double spender of the same e-coin.
It is an object of the present invention to provide e-cash or e-coins with certain highly desirable characteristics. The characteristics include the following:
1. Once a bank detects double spending (i.e. the same e-coin is deposited twice), the bank should have enough information to efficiently expose the identity of the double spender. However, one legitimate deposit of a particular e-coin should not provide the bank with enough information to compute the identity of the person who paid the particular e-coin to the depositor. PA1 2. The e-cash should be useable in the following transactions; (a) payment from payer to payee without revealing identity of payer, (b) deposit of money into the bank by the payee without revealing the identity of the payer, (c) an exchange transaction wherein a depositor gets a certain amount of fresh money from the bank in exchange for depositing the same amount of old money into the bank without revealing his/her identity, and (d) withdrawal from the bank. PA1 3. The system should be efficient. Specifically, the system should require as few real time operations as possible during transactions, especially at the money modules used by individual users as the money modules have limited processing power. As many operations as possible should be done in advance of and apart from the transactions which take place in real time.
The present invention provides an e-cash system which has these advantages.
The e-cash system of the present invention relies on certain prior art techniques. These prior art techniques are described below:
A. Public Key Cryptography
In a typical public key cryptographic system, each party i has a public key P.sub.i and a secret key S.sub.i. The public key P.sub.i is known to everyone, but the secret key S.sub.i is known only to party i. A clear text message m to user i is encrypted to form the cipher text message c using a public operation P which makes use of the public key P.sub.i known to everyone, i.e., c=P(m,P.sub.i). The cipher text message c is decrypted using a secret operation S which makes use of the secret key S.sub.i, i.e., m=S(c,S.sub.i). Only the party i which has the secret key S.sub.i can perform the secret operation to decrypt the encrypted message.
Public key cryptographic techniques may also be used for authentication. If it is true that P(S(m, S.sub.i),P.sub.i)=m, then the owner of the corresponding keys P.sub.i, S.sub.i could sign message m by producing s=S(m,S.sub.i), where s indicates the signature. The verifier, given m and s will verify m=P(s,P.sub.i). A signature system could be used for verification as follows: Challenge the party claiming to be i with message m and ask the party to sign the message m using his secret key S.sub.i, then verify the signature using P.sub.i.
An example of a public key cryptographic technique is the well known RSA technique. In accordance with this technique, a party i has a public key in the form of an exponent e and modulus N and a secret key in the form of an exponent d. Thus,a party with a message to send to party i encrypts the message m to form c.tbd.m.sup.e mod N. The party i can then decrypt c to obtain m by performing the operation m=c.sup.d mod N.
Another public key crytographic technique is the Rabin modular square root. In this technique, the secret operation involves obtaining a modular square root and the public operation involves a modular squaring operation.
B. EL Gamal Signature Scheme
Let P.sub.i and S.sub.i be the public and secret keys of user i, where P.sub.i =.alpha..sup.Si mod p, where p is a large prime or a product of large primes, and .alpha. is a generator in Z.sub.p.sup.*. An El-Gamal signature by user i, on message m is an ordered pair s=(u,v), for which EQU P.sub.i.sup.u .multidot.u.sup.v .tbd..alpha..sup.m mod p (1)
Thus a recipient of a signature can easily verify it. To create a signature, user i chooses a random number r, and computes u=.alpha..sup.r mod p. From eq (1) it follows that: EQU S.sub.i .multidot.u+r.multidot.v.tbd.m mod p-1 (2)
Hence i, who is the only one who knows S.sub.i, can compute v, provided gcd(r,p-1)=1. The El Gamal signature scheme is disclosed in T. El Gamal "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Trans IT, Vol. IT-31, No. 4, July, 1985, pp. 469-472.
The El-Gamal signature system has the curious property that if the signer i tries to use the same r twice to sign two different messages, then these two signatures expose his secret key S.sub.i. To see how double use of r exposes S.sub.i, note that from eq (2) that EQU S.sub.i .multidot.u+r.multidot.v.sub.1 .tbd.m.sub.1 mod p-1; S.sub.i .multidot.u+r.multidot.v.sub.2 .tbd.m.sub.2 mod p-1 (3)
Hence, EQU r(v.sub.1 -v.sub.2).tbd.(m.sub.1 -m.sub.2) mod p-1 (4)
If gcd (v.sub.1 -v.sub.2, p-1)=1, anybody knowing the messages m.sub.1, m.sub.2 and their signatures (u,v.sub.1), (u,v.sub.2) can find r, and if gcd(v,p-1)=1, then S.sub.i can be computed. This unique property of the El Gamal signature scheme is used as the basis for an e-cash system according to the invention in which the identity of a double spender of a particular e-coin is exposed.
Other signature schemes such as NIST-DSS and Schnorr also have the property that if two distinct messages are signed using the same random element (e.g. r), then the secret key of the signer can be computed by anyone having the messages, the signatures and public information such as the public key of the signer. As used herein, the term El Gamal family of signatures refers to signature schemes with this property.
C. Blind Signature
The idea of a blind signature is to mimic a situation in which a person signs a closed envelope. The envelope includes some document and a carbon paper, so that the signature appears (via the carbon paper) on the document, without the signer knowing the contents of the document. The recipient can later fetch the signed document from the envelope. This seemingly bizarre idea proves very helpful in establishing nontraceability. A blind signature may be implemented using RSA as follows. The signer is associated with N,e,d (public modulus, public exponent, and secret exponent, respectively). The secret message to be signed is m. The recipient picks a random x.epsilon.Z.sub.N.sup.*, and presents a "message-in-envelope" c.tbd.x.sup.e .multidot.m mod N to the signer, who signs it, i.e. computes c.sup.d .tbd.x.multidot.m.sup.d mod N, from which the recipient, and only the recipient (who knows x), can compute the signed message m.sup.d .tbd.c.sup.d x.sup.-1 mod N.
The public key cryptography techniques described above are used to provide a unique e-cash system according to the invention.